The present invention relates to data communication. apparatus and methods for communicating data. More specifically, the present invention relates to data communications apparatus and methods of communicating data in which data is punctured or repeated.
Digital communications systems are arranged to communicate data by representing the data in a form which facilitates transmission of the data via a medium through which communication is affected. For example, in a case of radio communications, the data is represented as radio signals and transmitted between transmitters and receivers of the communications system via the ether. In the case of broadband telecommunications networks, the data may be represented as light and communicated via, for example, a fibre optic network between transmitters and receivers of the system.
During transmission of data, bits or symbols of the communicated data can be corrupted to the effect that these bits or symbols can not be correctly determined at the receiver. For this reason, the data communications systems often include means for mitigating the corruption of the data which occurs during transmission. One of these means is to provide transmitters of the system with encoders, which encode the data prior to transmission, in accordance with an error control code. The error control code is arranged to add redundancy to the data in a controlled way. At the receiver, errors occurring during transmission may be corrected by decoding the error control code, thereby recovering the original data. The decoding is effected using an error decoding algorithm corresponding to the error control code, which is known to the receiver.
After data has been encoded, there is often a requirement to puncture data bits or symbols from a block of encoded data before transmission of that data. The term puncturing as used herein refers to a process of cancelling or deleting bits from an encoded data block to the effect that the punctured bits are not transmitted with that data block puncturing might be required because, for example, a multiple access scheme, which serves to effect communication of the data via the data bearing media, requires the data to be formatted into blocks having a pre-determined size, which does not correspond to the size of the encoded data frame. In order to fit the encoded data frame into the transport data block of the pre-determined size, therefore, data bits from the encoded data frame are either punctured, to decrease the size of the encoded data block, in a case where the encoded data frame is larger than the size of the transport block, or repeat bits of the encoded data frame in a case where the encoded data frame is smaller than the pre-determined size of the transport block.
As will be appreciated, the data frames may be transmitted un-encoded in the transport data block. In this case, it is not appropriate to puncture the data frame in order to fit the data frame into the transport data block, a plurality of transport data blocks must be used to convey the data frame. In a case where the data frame is smaller than the transport data block, then the data bits or symbols are repeated to an extent necessary to fill the remainder of the transport data block.
As is familiar to those skilled in the art, an effec t of puncturing an encoded data frame, is that a probability of correctly recovering the original data is reduced. Furthermore, the performance of known error control codes and decoders for these err or c control codes is best when the errors occurring during transmission of the data are caused by Gaussian noise, with an effect that the errors are independently distributed throughout the transport data block. Similarly, therefore, if an encoded data frame is to be punctured, the positions within the encoded data frame at which bits are punctured, should be separated from each other as far as possible. As such, the puncturing positions should be evenly distributed throughout the frame. Similarly, because errors during transmission often occur in bursts, particularly in the case of radio communications systems which do not employ interleaving, positions within an encoded or an un-encoded data frame, at which data bits are to be repeated, should be arranged to be evenly separated throughout the frame.
Known methods of selecting the positions of bits or symbols to be punctured or repeated within an encoded data frame, include dividing the number of bits or symbols within a frame, by the number of bits or symbols to be punctured and selecting positions at integer values corresponding to the division. However, in a case where the number of bits to be punctured is not an integer division of the frame, an equi-distant separation of punctured or repeated positions does not result, providing the disadvantage that some positions may be closer than this integer, and in some cases even adjacent one another.
U.S. Pat. No. 4,908,827 is directed to a method and apparatus for puncturing excessive bits of convolutional data. By way of example, every third bit is removed. First and second puncturing is performed to get the data stream properly formatted.
PCT published application WO 97/16899 sets out a method and apparatus for combining frames to facilitate data transmission. The combination includes puncturing of excessive data bits. The selection method is left to one skilled in the art.
PCT published application WO 96/24993 is concerned with the smooth insertion of null data within a data stream. The application is not concerned with removal or puncturing of any data bits. Rather, the application xe2x80x9csmoothlyxe2x80x9d fills in the empty spaces about occupied bytes such that the data carrying bytes can be effectively communicated in fixed frames. The application makes use of Bresenham""s algorithm in the selection of an smooth placement of null bytes. The placement is intended to effect buffer and latency savings.
It is an object of the present invention to provide a means for puncturing or repeating data bits from a data frame in a single iteration, in which the positions of the punctured or repeated bits are substantially equi-distant throughout the frame.
The present invention resides generally in a data communication apparatus in which frames of data are converted into blocks for transmission by puncturing or repeating bits or symbols from the frame at positions determined in accordance with a selection algorithm, the positions being equally distributed throughout the data frame.
According to the present invention there is provided a data communications apparatus which operates to communicate data frames, the apparatus comprising means for converting the data frames into data blocks for transmission, which data blocks are of a size which is different to that of the data frames, the means for converting the data frames including means for puncturing or repeating bits or symbols at positions within the data frame determined in accordance with a selection strategy, wherein the selection strategy is arranged to provide a substantially equal distribution of the positions throughout the data frame.
A converter means serves to convert the data frames into data transport blocks having a different size to that of the data frames, and includes means for puncturing or repeating the data frame at positions within the data frame determined in accordance with a selection strategy. By arranging for the selection strategy to made to the effect that the positions to be repeated or punctured are equally distributed throughout the data frame, as opposed to attempting to make the positions equi-distant from each other, the selected positions will be such as to provide an optimum mean separation of the positions within the data frame.
The selection strategy may be affected by a selection algorithm which operates in accordance with the size of said data frame, in combination with the number bits or symbols to be punctured or repeated. The selection algorithm may be a digital differential analyzer-type algorithm, or the like.
The Digital Differential Analyser algorithm is known per se in the field of computer graphics for graphically representing lines in two dimensions for use in computer generated images. The Digital Differential Analyser is disclosed in a publication entitled xe2x80x9cComputergrafik: Einfxc3xchrung-Algorithmen-Programmentwicklungxe2x80x9d, by Jxc3xcrgen Plate, pages 55 to page 65, ISBN Number 3-7723-5006-2 and is further described in an article in association with drawing lines, entilted ,Bresenham""s Line Algorithm by Sunir Shah, 15 Jan. 1997, in a publication xe2x80x9cWASTExe2x80x94Warfare by Artificial Strategic and Tactical Enginesxe2x80x9d, published on the Internet at address xe2x80x9chttp://intranet.on.ca/-sshah/waste/art7.htmlxe2x80x9d.
The use of an adapted version of a digital differential analyser-type algorithm, provides particular advantages. For example, the puncturing of adjacent bits is avoided, punctured bits are equally distributed over the transmitted data frame, only one pass is required for puncturing with any desired rate, and the same selection algorithm of substantially low complexity, can be used for puncturing and repetition. Furthermore the algorithm facilitates adaptation to additional constraints for the position of selected bits, such as that required by a Potential Puncturing Grid (PPG), as described in xe2x80x9cSpecial Mobile Group 2xe2x80x9d UMTS-11 Tdoc 229/98, entitled xe2x80x9cService Multiplexingxe2x80x9d.
The data communications apparatus may further include an encoder which operates to encode the data frame in accordance with an encoding algorithm. The encoding algorithm may be an error control encoding algorithm. For example the encoding algorithm, may operate in accordance with a block code such as a B-C-H, Reed-Solomon or Hamming code. Furthermore the encoding algorithm could be a convolutional code, a turbo code or a product code.
According to a further aspect of the present invention there is provided a method of communicating data frames, comprising the step of converting said data frames into data blocks for transmission, which data blocks are of a different size to that of the data frames, the step of converting the data frames including puncturing or repeating bits or symbols at positions within the data frame determined in accordance with a selection strategy, wherein the selection strategy is arranged to provide an equal distribution of the positions throughout the data frame.
One embodiment of the present invention will now be described, by way of example only, with reference to the accompanying drawings wherein;